Service providers and device manufacturers (e.g., wireless, cellular, etc.) are continually challenged to deliver value and convenience to consumers by, for example, providing compelling network services. For example, location-aware applications and services are becoming popular on mobile devices (e.g., smart phones, tablets, etc.). Such applications and services rely on both real-time as well as historical location information to better predict and adapt the applications and services to user behavior. Benefits exist in storing historical location information on the mobile devices. Yet mobile devices are usually constrained by the available on-device storage. Accordingly, service providers and device manufacturers face significant technical challenges in storing historical location information on mobile devices for use with location-aware applications and services.